'''
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，
在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），
因而在从后向前扫描过程中，找到排序位置后，需要将已排序元素逐步向后挪位，为新元素提供插入空间。
算法步骤：
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。
时间复杂度：
最好情况：当输入数组已经是排序好的，此时的时间复杂度为O(n)，因为每次循环，新元素都只需要和已排序序列的最后一个元素比较一次，即可确定其位置。
平均情况和最坏情况：当输入数组是逆序时，时间复杂度达到最高，为O(n ^2 )。因为每次插入新元素时，都可能需要和已排序序列中的所有元素进行比较，
并可能移动所有已排序的元素。
空间复杂度：
插入排序的空间复杂度为O(1)，因为这是一个in-place排序算法，它只需要固定的额外空间来存储一些变量（如索引和临时变量），
而不依赖于输入数组的大小。
优点：
实现简单；
对于小规模数据或基本有序的数据效率高；
稳定性排序（即相等元素的相对顺序在排序前后不会改变）。
缺点：
对于大规模数据，效率较低；
数据移动较多，尤其是当数据规模较大且基本无序时。
插入排序因其简单性和在特定情况下的效率，在某些应用中仍然很有用，尤其是在数据规模较小或基本有序时。然而，在处理大规模数据时，
更高效的排序算法（如快速排序、归并排序等）通常是更好的选择。
'''
class Solution:
    def insertionSort(self, arr):
        print('排序前：',arr)
        for i in range(1, len(arr)):
            flag =0     #定义标志如果未交换即大于最右边值则跳出当前循环
            for j in range(i, 0, -1):
                if arr[j] < arr[j - 1]:
                    arr[j], arr[j - 1] = arr[j - 1], arr[j]
                    flag = 1
                if flag==0:
                    break
        return arr
#示例
if __name__ == '__main__':
    arr = [1, 2, 3, 4, 5, 6, 7]
    arr1 = [3,9,8,1,5,6,10]
    print('排序后：',Solution().insertionSort(arr))
    print('排序后：',Solution().insertionSort(arr1))
